#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
//LeetCode 79. Word Search
struct Node
{
    int x;
    int y;
    //int visited;
    Node(int _x, int _y):x(_x), y(_y) {}
};

void backtrack(vector<vector<char>>& board, string& word, int& count, int x, int y)
{
    vector<vector<bool>> used(board.size(), vector<bool>(board[0].size()));
    queue<Node> q;
    q.push(Node(x, y));
    int flag = 0;//用于判断是否找到下一个字母,每次循环将其值重新置为0代表找寻下一个字母
    //每次循环代表找下一个字母
    while(!q.empty())
    {
        int size = q.size();
        flag = 0;
        //执行一次循环代表找一个字母
        for(int i=0;i<size;i++)
        {
            Node node = q.front();
            cout<<"the node is:"<<board[node.x][node.y]<<endl;
            if(node.x-1>=0&&board[node.x-1][node.y]==word[count]&&!used[node.x-1][node.y])
            {
                q.push(Node(node.x-1, node.y));
                flag++;
            }
            if(node.x+1<board.size()&&board[node.x+1][node.y]==word[count]&&!used[node.x+1][node.y])
            {
                q.push(Node(node.x+1, node.y));
                flag++;
            }
            if(node.y-1>=0&&board[node.x][node.y-1]==word[count]&&!used[node.x][node.y-1])
            {   
                q.push(Node(node.x, node.y-1));
                flag++;
            }
            if(node.y+1<board[0].size()&&board[node.x][node.y+1]==word[count]&&!used[node.x][node.y+1])
            {
                q.push(Node(node.x, node.y+1));
                flag++;
            }
            used[node.x][node.y] = true;
            q.pop();
        }
        if(flag > 0)
            count++;
    }   
}
bool exist(vector<vector<char>>& board, string word) {
    int count = 0;
    vector<vector<bool>> used(board.size(), vector<bool>(board[0].size()));
    for(int i=0;i<board.size();i++)
    {
        for(int j=0;j<board[i].size();j++)
        {
            if(board[i][j] == word[0])
            {
                cout<<"the 1st word is: "<<board[i][j]<<endl;
                count++;
                backtrack(board, word, count, i, j);
                if(count == word.size())
                    return true;
                else
                    count = 0;
            }
        }
    }
    return false;
}
int main()
{
    vector<vector<char>> board = {
        { 'A','B','C','E' },
        { 'S','F','E','S' },
        { 'A','D','E','E' }
    };
    string word = "ABCESEEEFS";
    if(exist(board, word))
        cout << "true" << endl;
    else
        cout << "false" << endl;
    return 0;
}